package com.ruirui.linklist;

import java.util.AbstractList;
import java.util.HashMap;
import java.util.LinkedList;

public class MyLinkList<E>  extends AbstractList<E> {
    private Node<E> first; //头结点
    private Node<E> last; // 尾节点
    private int size; // 容量

   static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(E item, Node<E> next, Node<E> prev) {
            this.item = item;
            this.next = next;
            this.prev = prev;
        }
    }
    public MyLinkList() {

    }

    @Override
    public boolean add(E e) {
       //  |    | -> 1
        Node<E> l = last;
        Node<E> newNode = new Node<>(e, null, l);
        // 尾节点
        last = newNode;
        if (l == null) {
            //尾巴是空 证明没头
            first = newNode;
        } else {
            //连接
            l.next = newNode;
        }
        size++;
        return true;
    }


    @Override
    public E get(int index) {
         if (index >= size)
            throw new IndexOutOfBoundsException();
         // 折半遍历
        Node<E> node;
        if (index < (size>>1)){
            node = first;
             for (int i = 0; i < index; i++) {
                 node = node.next;
             }
        }else {
            node = last;
             for (int i = size-1; i > index; i--){
                 node = node.prev;
             }
        }
        return node.item;

    }

    @Override
    public int size() {
        return size;
    }
    public static void main(String[] args) {
//        new LinkedList<>();

        MyLinkList<String> list = new MyLinkList<>();
        list.add("1");
        list.add("2");
        System.out.println(list);
        System.out.println(list.get(1));
        HashMap<String, String> map = new HashMap<>();
    }
}
